/**
 * Created by L.jp
 * Description:
 * User: 86189
 * Date: 2022-07-10
 * Time: 10:21
 */
//对数器实现的原理就是使用Math.Random()来实现，random（）返回的是一个double的小数，并且是等概率返回的，下面我们将进行验证。
    //对数器的作用：
    /*对数器的作用
    对数器是通过用大量测试数据来验证算法是否正确的一种方式。
    在算法笔试的时候，我们经常只能确定我们写出的算法在逻辑上是大致正确的，但是谁也不能一次性保证绝对的正确。
    特别是对于一些复杂的题目，例如贪心算法，我们往往无法在有限时间内用数学公式来推导证明我们程序的正确性。
    而且在线的OJ一般只会给出有数的几个简单的samples，可能我们的算法在这些简单的samples偶然通过了，
    但是在一些复杂的samples处却出现了问题。这时我们无法使用复杂的samples来分析调试我们的代码，
    人工设计样例来测试代码的效率又太低，而且不能确保考虑各种特殊情况。因此，能随机产生不同情况的数据的对数器就派上了用场。

    对数器，简而言之，就是一个绝对正确的方法和能产生大量随机样例的随机器的组合。
    看到这里，有些童鞋有疑问了。既然我们知道了绝对正确的方法，直接用这个方法不就好了嘛？
    请注意，算法追求的不是解决问题，而是高效率的解决问题。对于一个数组的排序，
    如果笔试中要求的时间复杂度是O(NlogN)，但是你却写了一个冒泡排序的算法交上去了，这时OJ就会提示：
    Time Limit Exceeded
    而在对数器中，我们要求的绝对正确的算法是没有时间和空间复杂度的限制的，唯一的要求是确保绝对正确。
    因为只有绝对正确，我们才能通过样例的比对，发现我们的代码是在哪里出了错误。

    相关概念
    有一个你想要测的方法a；
    实现一个绝对正确但是复杂度不好的方法b；
    实现一个随机样本产生器；
    实现对比算法a和b的方法；
    把方法a和方法b比对多次来验证方法a是否正确；
    如果有一个样本使得比对出错，打印样本分析是哪个方法出错；
    当样本数量很多时比对测试依然正确，可以确定方法a已经正确。
    其中要注意以下几点：
    
    随机产生的样本应该是小数据集，但是要进行多次(10w+)的对比。小数据集是因为方便对比分析，多次比对是要覆盖所有的随机情况。
    算法b要保持正确性。*/
public class MyRandom {
    public static void main (String[] args) {
        System.out.println("测试开始！");
        //Math.Random() ---> (double) [0,1)
        //验证Math.Random()的等概率返回数据
        //随机生成10000000次
        int testTimes=10_0000_00;
        //统计一个数出现的次数
        int count=0;
        for(int i=0;i<testTimes; i++){
            if(Math.random() < 0.625){
                count++;
            }
        }
        //打印概率
       // System.out.println((double) count / (double) testTimes);  //结果可是逻辑上的概率和我们的猜想是一样的，random就是等概率返回的
        
        //接下来验证random返回任意范围的随机数的概率
        count=0;
        for(int i = 0; i < testTimes; i++){
            //random生成[0,8)的随机数的次数
            if(Math.random()* 8 < 4){ //返回的的是零点几，一点几。。。。。到七点几的任意数，逻辑上出现零点几到三点几的概率是一半
                count++;
            }
        }
        //System.out.println((double) count / (double) testTimes);
        
        //如果要返回的是int类型
        int k=9;
        int[] counts=new int[k];//统计[0,8]任意数出现的次数
        for(int i=0;i<testTimes;i++){
            int ans=(int) (Math.random() * k); //应该返回的是[0,8]的数
            counts[ans]++;
        }
//        for(int j=0;j<counts.length; j++){
//            System.out.println(j +"出现了"+counts[j]+" 次！" ); //从0到8出现的次数都是一样的，说明random的等概率返回
//        }
        
        //验证random返回随机数的概率由x变为x²
        count=0; //验证
        double x=0.3; //作为一个对比的数据
        for(int i = 0; i < testTimes; i++){
//            if(xToxPower2()<x){
//                count++;
//            }
            if(xToxPower3()<x){
                count++;
            }
        }
//        System.out.println((double) count /(double) testTimes);
//        //System.out.println(Math.pow( x,2 ));
//        System.out.println(Math.pow( x,3 ));
      
      //验证0到1生成的次数，看1~5生成的是不是等概率
        count=0;
        for(int i=0;i<testTimes; i++){
            if(f2()==0){
                count++;
            }
        }
      //  System.out.println((double) count / (double) testTimes);
        
        
        //验证1~5的随机生成1~7的随机
        count=0;
        counts=new int[8]; //用来存储统计好的1~7生成的随机数的个数
        for(int i = 0; i < testTimes; i++){
            int num=g();
            counts[num]++;
        }
        for(int i=0;i<8;i++){
            System.out.println(i+"出现了 "+counts[i]+" 次！");
        }
      
    }
    //返回[0,1)的随机数出现的概率的平方
    public static  double xToxPower2(){
        return Math.max(Math.random(),Math.random());
    }
    //返回[0,1)的随机数出现的概率的平方
    public static  double xToxPower3(){
        return Math.max(Math.random(),Math.max(Math.random(),Math.random()));
    }
    
    //由1~5的随机变成1~7的随机
    //给定f2函数是生成1~5的随机数，这个不能动，这个是已知的函数，利用这个函数进行求解生成1~7的随机数
    public static int f1(){
        return (int) (Math.random()*5)+1;
    }
    //把生成1~5的随机数改成0 1等概率生成器
    public static  int  f2(){
        int ret=0;
        do{
            ret=f1();
        
        }while ( ret==3 );  //得到3继续循环
        //1,2 返回0  4,5返回1   ，那么1和2出现的概率由原来的20%变为25%;
        return ret<3 ? 0 : 1;
    }
    //1~7可以由0~6生成随机+1得到
    //0~6怎么生成，就是利用三个二进制位即可，
    //这里先生成0~7的数等概率
    public static int f3(){
        return (f2()<<2)+(f2()<<1)+(f2()<<0);
    }
    //0~6等概率的实现，从生成的0~7中，遇到7就返回循环，直到遇到的不是7
    public  static int f4() {
        int ret=0;
        do{
            ret=f3();
        }while ( ret==7 );
        return ret;
    }
    //生成1~7的随机数
    public static int g(){
        return f4()+1;
    }
    
    //由0和1的不等概率，变成0和1的等概率
    //0: p   1:1-p
    //那么就可以假设有一个函数会不等概率生成0和1，调用两次这个函数，如果两次生成的是一样的，那么就重来，直到生成的不一样，即一个生成0，一个生成1
    public static  int x(){
        //随机设置不等概率
        return Math.random()<0.6 ? 0 :1;
    }
    //变成的等概率返回0和1
    public static  int y(){
        int  ret=0;
        do{
            ret=f4();
        }while ( ret==f4() );
        return ret;
    }
    
}
